
import time, random, math
from operator import itemgetter

from scripts.utils import constants, input_reading
from dexen.libs import dexen_api, constants as dc

""" GLOBALS """
script_api = dexen_api.getScriptApi()
boxes = input_reading.read_input()
n_boxes = len(boxes)

objectives = ["min_width", "min_height"]
focus = 0

def generate_encoding(gamma_x, gamma_y, encoding):
    for i, box_no in enumerate(gamma_x):
        encoding[box_no] = dict(x=i)
    for i, box_no in enumerate(gamma_y):
        encoding[box_no]['y'] = i    

def mutate(individual):
    for i in range(n_boxes/20):
        box_no = random.randint(0, n_boxes - 1)
        individual['orient'][box_no] = 1 - individual['orient'][box_no]

def generate_child(parent1, parent2):
    child = {
        "gamma_x":range(n_boxes),
        "gamma_y":range(n_boxes),
        "encoding":range(n_boxes),
        "orient":range(n_boxes)
    }
    
    for i in range(n_boxes):
        child['gamma_x'][i] = parent1['gamma_x'][i]
        child['gamma_y'][i] = parent1['gamma_y'][i]
        child['orient'][i] = parent1['orient'][i]
    
    left_x = random.randint(0, n_boxes - 2)
    right_x = random.randint(left_x + 1, n_boxes - 1)
    
    neighbor_ids = []
    for i in range(left_x, right_x + 1):
        neighbor_ids.append(parent1['gamma_x'][i])
    
    rows = [] 
    """ This keeps the y coordinates of the ones in the window """
    for i in neighbor_ids:
        rows.append(parent1['encoding'][i]['y'])
    rows.sort()
    
    neighbor_ids.sort(cmp=lambda a,b: parent2['encoding'][a]['x'] - parent2['encoding'][b]['x'])
    cnt = 0
    for i in range(left_x, right_x + 1):
        child['gamma_x'][i] = neighbor_ids[cnt]
        cnt = cnt + 1
    
    neighbor_ids.sort(cmp=lambda a,b: parent2['encoding'][a]['y'] - parent2['encoding'][b]['y'])
    cnt = 0
    for i in rows:
        child['gamma_y'][i] = neighbor_ids[cnt]
        cnt = cnt + 1
    
    generate_encoding(child['gamma_x'], child['gamma_y'], child['encoding'])
    mutate(child)
    
    child['state'] = constants.ALIVE
    return child
        
def generate_children(parent1, parent2):    
    child1 = generate_child(parent1, parent2)
    child2 = generate_child(parent2, parent1)
    return [child1, child2]

def perturb_parents(population):
    shuffle_size = len(population) / 10
    pos = random.randint(0, len(population) - shuffle_size)
    shuffled_sublist = population[pos:pos + shuffle_size]
    random.shuffle(shuffled_sublist)
    population[pos:pos + shuffle_size] = shuffled_sublist
    return 


def reproduction(population):
    population.sort(key = lambda x : x[objectives[focus]])
    perturb_parents(population)

    """ Check the population size if it is even """
    new_gen = []    
    for i in range(0, len(population) - 1, 2):
        new_gen.extend(generate_children(population[i], population[i+1]))
    
    if len(population) % 2 != 0:
        new_gen.append(generate_child(population[len(population)-2], population[len(population)-1]))
    
    return new_gen

def feedback():
    population = script_api.downloadIndividuals(
        select = ("gamma_x", "gamma_y", "encoding", "orient", "area", "min_width", "min_height", "state"),
        where = (
            ("state", dc.EQUAL, constants.ALIVE),             
            ("area", dc.NOT_EQUAL, None),
        ), 
        count = constants.FEEDBACK_SIZE,
    )
    
    global focus, objectives
    cur = time.time()
    #print "I am in feedback"    
    
    selection(population)
    #environmental_selection(population)
    parents = [ind for ind in population if ind['state'] == constants.ALIVE]
    assert len(parents) == constants.FEEDBACK_SIZE / 2
    
    new_gen = reproduction(parents)
    focus = 1 - focus
    #print str(time.time() - cur), "seconds."
    script_api.uploadIndividuals(population + new_gen)

def dominates(ind1, ind2):
    return (ind1['min_width'] <= ind2['min_width'] and ind1['min_height'] < ind2['min_height']) or \
           (ind1['min_width'] < ind2['min_width'] and ind1['min_height'] <= ind2['min_height'])

def calculate_strength(individuals):
    for ind1 in individuals:
        ind1['strength'] = 0
        for ind2 in individuals:
            if dominates(ind1, ind2):
                ind1['strength'] += 1

def calculate_raw_fitness(individuals):
    for ind1 in individuals:
        ind1['raw_fitness'] = 0
        for ind2 in individuals:
            if dominates(ind2, ind1):
                ind1['raw_fitness'] += ind2['strength']

def calculate_fitness(individuals):
    for ind in individuals:
        ind['fitness'] = ind['raw_fitness'] + ind['density'] 

def get_distance(ind1, ind2):
    return math.sqrt((ind1['min_width'] - ind2['min_width'])**2 + (ind1['min_height'] - ind2['min_height'])**2)

def calculate_distances(individuals):
    for ind1 in individuals:
        ind1['distances'] = []
        for ind2 in individuals:
            ind1['distances'].append({"ind" : ind2, "distance" : get_distance(ind1, ind2)})
        ind1['distances'].sort(key = lambda x:(x['distance']))

def calculate_density(individuals):
    k = int(math.sqrt(constants.FEEDBACK_SIZE)) 
    for ind in individuals:
        ind['density'] = 1.0 / (ind['distances'][k]['distance'] + 1) #????? 1 or 2 

def pop_keys(individuals):
    for ind in individuals:
        ind.pop('strength')
        ind.pop('raw_fitness')
        ind.pop('fitness')
        ind.pop('density')
        ind.pop('distances')
        if ind.has_key('removed'):
            ind.pop('removed')

def get_distance_k(ind, k):
    cnt = 0
    pos = 0
    while cnt < k:
        assert pos < len(ind['distances'])
        if ind['distances'][pos]['ind']['removed'] == False:
            cnt += 1
        pos += 1
    return ind['distances'][pos-1]['distance']
    
            
def smaller(ind1, ind2, N):
    for k in range(N):
        dist1 = get_distance_k(ind1, k)
        dist2 = get_distance_k(ind2, k)
        if dist1 > dist2:
            return False
        if dist1 < dist2:
            return True
    return True

def remove_individual(min_ind, individuals):
    for i, ind in enumerate(individuals):
        if ind is min_ind:
            individuals.pop(i)
            

def archive_truncation(individuals, N):
    while (len(individuals) > N):
        min_ind = individuals[0]
        for ind in individuals[1:]:
            if smaller(ind, min_ind, len(individuals)):
                min_ind = ind
        min_ind['removed'] = True
        #individuals.remove(min_ind)
        remove_individual(min_ind, individuals) 

def environmental_selection(individuals):
    calculate_strength(individuals)
    calculate_raw_fitness(individuals)
    calculate_distances(individuals)
    calculate_density(individuals)
    calculate_fitness(individuals)
    
    for ind in individuals:
        ind['state'] = constants.DEAD
        
    next_archive = [x for x in individuals if x['fitness'] < 1]
    dominated_ones = [x for x in individuals if x['fitness'] >= 1]
    archive_size = len(next_archive)
    N = constants.FEEDBACK_SIZE / 2
    
    if archive_size < N:
        dominated_ones.sort(key = lambda x:(x['fitness']))
        next_archive.extend(dominated_ones[:N - archive_size])
    elif archive_size > N:
        for ind in individuals:
            ind['removed'] = False
        archive_truncation(next_archive, N)

    assert len(next_archive) == N
    for ind in next_archive:
        ind['state'] = constants.ALIVE
    pop_keys(individuals)
        
def selection(population):
    cur = time.time()
    population.sort(key = lambda x:(x["area"]))

    dead_inds = population[constants.FEEDBACK_SIZE / 2:]
    for ind in dead_inds:
        ind['state'] = constants.DEAD          
